import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Test {

    //滑动窗口


    //最小覆盖子串
    public String minWindow(String ss, String tt) {
        char[] s = ss.toCharArray();
        char[] t = tt.toCharArray();
        int[] hash1 = new int[128];//统计字符串t中每一个字符的频次
        int kinds = 0;
        for (char ch:t) {
            if (hash1[ch]++ == 0) kinds++;
        }
        int[] hash2 = new int[128];//统计窗口内每个字符的频次
        int minlen = Integer.MAX_VALUE,begin = -1;
        for(int left = 0,right = 0,count = 0;right<s.length;right++){
            char in = s[right];
            if(++hash2[in] == hash1[in]) count++;
            while(count == kinds){
                if (right-left+1 < minlen){
                    minlen = right-left+1;
                    begin = left;
                }
                char out = s[left++];
                if (hash2[out]-- == hash1[out]) count--;

            }
        }
        if (begin == -1) return new String();
        else return ss.substring(begin,begin+minlen);
    }


    //串联所有单词的子串
    public List<Integer> findSubstring(String s, String[] words){
        List<Integer> ret = new ArrayList<Integer>();

        Map<String,Integer> hash1 = new HashMap<String,Integer>();//保存字典中所有单词的频次
        for (String str:words) {
            hash1.put(str,hash1.getOrDefault(str,0)+1);
        }

        int len = words[0].length();
        int m = words.length;
        for (int i = 0; i < len; i++) {//执行次数，保证不同起始位置
            Map<String , Integer> hash2 = new HashMap<String,Integer>();
            for(int left = i,right = i,count = 0;right+len<= s.length();right+=len){
                String in = s.substring(right,right+len);
                hash2.put(in,hash2.getOrDefault(in,0)+1);
                if (hash2.get(in) <= hash1.getOrDefault(in,0)) count++;
                while(right-left+1 > len*m){
                    String out = s.substring(left,left+len);
                    if (hash2.get(out) <= hash1.getOrDefault(out,0)) count--;
                    hash2.put(out, hash1.get(out)-1);
                    left += len;
                }
                if(count == m) ret.add(left);
            }

        }
        return  ret;
    }




    //找到字符串中所有字母的异位词
    public List<Integer> findAnagrams(String ss, String pp) {
        List<Integer> ret = new ArrayList<Integer>();
        char[] s = ss.toCharArray();
        char[] p = pp.toCharArray();

        int[] hash1 = new int[26];
        for (char ch : p) {
            hash1[ch-'a']++;
        }

        int[] hash2 = new int[26];
        int m = p.length;
        for(int left=0, right =0, count =0;right<s.length;right++){
            char in = s[right];
            if(++hash2[in-'a'] <= hash1[in-'a']) count++;//进窗口 维护count
            if(right-left+1 > m){//判断
                char out = s[left++];
                //出窗口 维护count
                if(hash2[out-'a']-- <= hash1[out-'a']) count--;
            }
            //更新结果
            if (count == m) ret.add(left);
        }
        return ret;
    }



    //水果成篮
    //使用数组模拟哈希表
    public int totalFruit1(int[] f){
        int n = f.length;
        int[] hash = new int[n+1];

        int ret = 0;
        for(int left =0 , right = 0 ,kinds = 0;right<n;right++){
            int in = f[right];
            if (hash[in] == 0) kinds++;//维护水果种类
            hash[in] ++;//进窗口

            while (kinds > 2){// 判断
                int out = f[left];
                hash[out]--;
                if (hash[out] == 0) kinds--;
                left++;
            }
            ret = Math.max(ret,right - left + 1);
        }
        return ret;

    }
    //使用容器
    public int totalFruit(int[] f){
        Map<Integer,Integer> hash = new HashMap<Integer,Integer>();//统计窗口内水果的种类
        int ret = 0;

        for(int left = 0,right = 0;right < f.length;right++){
            int in = f[right];
            hash.put(in,hash.getOrDefault(in,0) + 1);//进窗口
            while(hash.size() > 2){
                int out = f[left];
                hash.put(out,hash.get(out)-1);//出窗口
                if (hash.get(out) == 0) hash.remove(out);//删除
                left++;
            }
            ret = Math.max(ret , right-left+1);
        }
        return  ret;
    }



    //将x减到0的最小操作数
    public int minOperations(int[] nums, int x){
        int sum = 0;
        for (int a: nums) {
            sum += a;
        }
        int target = sum-x;
        //处理细节
        if (target < 0) return -1;

        int ret = -1;
        for(int left = 0,right = 0,tmp = 0;right< nums.length;right++){
            tmp += nums[right];//进窗口
            while (tmp > target){//判断
                tmp -= nums[left++];//出窗口
            }
            if (tmp == target){
                ret = Math.min(ret, right-left+1);
            }
        }
        if(ret == -1) return ret;
        else return nums.length-ret;
    }



    //最大连续1的个数III
    public int longestOnes(int[] nums, int k){
        int ret = 0;
        for(int left = 0,right = 0,zero = 0;right< nums.length;right++){
            if (nums[right] == 0) zero++;
            while(zero > k){
                if (nums[left++] == 0) zero--;
            }
            ret = Math.max(ret , right-left+1);
        }
        return ret;
    }


    //无重复字符的最长子串
    public int lengthOfLongestSubstring(String ss){
        char[] s = ss.toCharArray();
        int[] hash = new int[128];//用数组模拟哈希表
        int left = 0,right = 0,n = ss.length();
        int ret = 0;
        while(right < n){
            hash[s[right]]++;//进窗口
            while (hash[s[right]] > 1){//判断
                hash[s[left++]]--;//出窗口
            }
            ret = Math.max(ret,right-left+1);//更新结果
            right++;
        }
        return ret;
    }



    //长度最小的子数组
    public int minSubArrayLen(int target, int[] nums){
        int n = nums.length,sum = 0,len = Integer.MAX_VALUE;
        for(int left = 0,right = 0;right<n;right++){
            sum+=nums[right];
            while(sum>=target){
                len = Math.min(len,right-left+1);
                sum-=nums[left++];
            }
        }
        return len == Integer.MAX_VALUE ? 0 : len;
    }
}
